package com.company.ljh.medium;
/**
 * 129
 *.给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
 *
 * 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
 *
 *  
 *
 * 例如，在下面的 3×4 的矩阵中包含单词 "ABCCED"（单词中的字母已标出）。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/ju-zhen-zhong-de-lu-jing-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

/**
 * @description:
 * @projectName:leet_code
 * @see:com.company.ljh.medium
 * @author:ljh
 * @createTime:2022/6/22 11:32
 * @version:1.0
 */
public class 矩阵中的路径 {

    public boolean exist(char[][] board, String word) {
        int [][] isUsed = new int[board.length][board[0].length];
        for(int i=0;i < board.length;i++){
            for(int j=0;j < board[0].length;j++){
                if(find(isUsed,board,i,j,word,0)){
                    return true;
                }
            }
        }
        return false;

    }
    private boolean find(int[][] isUsed,char[][] board,int i,int j,String word,int index){
        if(isUsed[i][j] == 1){
            return false;
        }
        isUsed[i][j] = 1;
        if(board[i][j] != word.charAt(index)){
            isUsed[i][j] = 0;
            return false;
        }else{
            if(index == word.length()-1){
                return true;
            }
            if(i > 0 &&find(isUsed,board,i-1,j,word,index+1)){
                return true;
            }
            if(i < board.length-1 &&find(isUsed,board,i+1,j,word,index+1)){
                return true;
            }
            if(j > 0 &&find(isUsed,board,i,j - 1,word,index+1)){
                return true;
            }
            if(j < board[0].length-1 &&find(isUsed,board,i,j + 1,word,index+1)){
                return true;
            }
        }
        isUsed[i][j] = 0;
        return false;
    }
}
